package mo.leetcode_top;

import java.util.Arrays;
import java.util.PriorityQueue;

public class L502 {

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {

        boolean speedUp = true;
        for (int c: capital) {
            if (w < c) {
                speedUp = false;
            }
        }
        if (speedUp) {
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for (int p: profits) {
                heap.add(p);
                if (heap.size() > k) heap.poll();
            }
            for (int h: heap) w += h;
            return w;
        }

        int n = profits.length;
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }

        Arrays.sort(arr, (a, b) -> (a[0] - b[0]));

        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (y - x));
        int cur = 0;

        int min = Math.min(k, n);
        for (int i = 0; i < min; i++) {
            while (cur < n && arr[cur][0] <= w) {
                pq.add(arr[cur][1]);
                cur++;
            }

            if (!pq.isEmpty()) {
                w += pq.poll();
            } else {
                break;
            }
        }

        return w;
    }

}
